package com.example.sort;

public class RodCuttingProblem {
    // 价格表，下标表示长度，值表示对应长度的价格
    private static int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    // 自底向上的动态规划实现
    public static int bottomUpRodCut(int n) {
        int[] r = new int[n + 1]; // r[i]表示长度为i的钢条的最大收益
        int[] s = new int[n + 1]; // s[i]表示长度为i的钢条最优切割后的第一段长度

        //从长度1开始，逐步计算到长度n的最大收益。
        for (int i = 1; i <= n; i++) {
            int maxRevenue = Integer.MIN_VALUE;
            //遍历所有可能的切割点j（从1到i），计算切割后的收益 p[j] + r[i - j]。
            for (int j = 1; j <= i; j++) {
                //如果当前计算的收益大于之前记录的最大收益 maxRevenue，则更新 maxRevenue 和切割方案 s[i]。
                if (p[j] + r[i - j] > maxRevenue) {
                    maxRevenue = p[j] + r[i - j];
                    s[i] = j;
                }
            }
            //最后将最大收益存储到 r[i] 中。
            r[i] = maxRevenue;
        }
        
        // 输出切割方案
        System.out.print("切割方案: ");
        int remainingLength = n;
        //从长度n开始，通过 s 数组回溯每一步的最优切割点，直到剩余长度为0。
        while (remainingLength > 0) {
            //输出每次切割的长度，形成完整的切割方案。
            System.out.print(s[remainingLength] + " ");
            remainingLength -= s[remainingLength];
        }
        System.out.println();
        
        return r[n];
    }

    public static void main(String[] args) {
        int n = 9; // 钢条长度
        int maxRevenue = bottomUpRodCut(n);
        System.out.println("最大收益: " + maxRevenue);
    }
}